package video.simple100;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 *21. 合并两个有序链表
 */
public class LeetCode21 {

    @Test
    public void test() {

//        输入：l1 = [1,2,4], l2 = [1,3,4]
//        输出：[1,1,2,3,4,4]
        ListNode l1 = new ListNode(1, new ListNode(2, new ListNode(4)));
        ListNode l2 = new ListNode(1, new ListNode(3, new ListNode(4)));
        ListNode listNode = mergeTwoLists(l1, l2);
        while (listNode != null) {
            System.out.print(listNode.val + "  ");
            listNode = listNode.next;
        }
    }


    /**
     * 1、我们把 l1，l2两个链表的 用 list 保存一下， （也可以用数组）
     * 2 、排序
     * 3、报排序后的结果生成一个链表返回
     * @param l1
     * @param l2
     * @return
     */
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        List<Integer> list = new ArrayList<>();
        while (l1 != null) {
            list.add(l1.val);
            l1 = l1.next;
        }
        while (l2 != null) {
            list.add(l2.val);
            l2 = l2.next;
        }
        // 排序
        Collections.sort(list);
        //
        ListNode vo = new ListNode();
        ListNode nextVo = vo;
        //
        //vo ->   nextVo ->   nextVo ->   nextVo
        //          1           2            3
        // 1 2 3 4 5 6
        for (Integer val : list) {
            nextVo.next = new ListNode(val);
            nextVo = nextVo.next;
        }
        return vo.next;
    }


    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

}
